package sort.swap_sort;

import java.util.Arrays;

/**
 * 时间复杂度：<br/>
 * 平均: O(n ^ 2) <br/>
 * 最优(即数组有序): O(n), 最少比较 n - 1 次 <br/>
 * 稳定 <br />
 *
 * @author yzh
 * @data 2021/3/24 21:26
 */
public class BubbleSort {
    public static void main(String[] args) {
//        int[] nums = new int[]{12, -2, 21, 9, -1};
        int[] nums = new int[]{4, -1, 2, 9, 10};
//        method(nums);
        maopao(nums);
        System.out.println(Arrays.toString(nums));
    }

    public static void maopao(int[] nums) {
        int len = nums.length;
        for (int i = 1; i < len; i++) {
            for (int j = 0; j < len - i; j++) {
                if (nums[j] > nums[j + 1]) {
                    int tmp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = tmp;
                }
            }
        }
    }

    public static void method(int[] nums) {
        // 每次排序把最小的数字放到最前
        int len = nums.length;
        for (int i = 1; i < len; i++) {
            for (int j = len - 1; j >= i; j--) {
                if (nums[j] < nums[j - 1]) {
                    int tem = nums[j - 1];
                    nums[j - 1] = nums[j];
                    nums[j] = tem;
                }
            }
        }
    }

    /**
     * 每次排序都把最大的数字放到最后
     * 确定每趟交换到哪个位置为止
     *
     * @param nums
     */
    public static void method01(int[] nums) {
        int len = nums.length;
//        for (int i = len - 2; i >= 0; i--) {
//            for (int j = 0; j <= i; j++) {
//                if (nums[j] > nums[j + 1]) {
//                    int tem = nums[j];
//                    nums[j] = nums[j + 1];
//                    nums[j + 1] = tem;
//                }
//            }
//        }
        for (int i = 1; i < len; i++) {
            for (int j = 0; j < len - i; j++) {
                if (nums[j] > nums[j + 1]) {
                    int tem = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = tem;
                }
            }
        }
    }

    /**
     * 每次排序都把最小的数字放到最前面
     *
     * @param nums
     */
    public static void method02(int[] nums) {
        int len = nums.length;
        for (int i = 1; i < len - 1; i++) {
            for (int j = len - 1; j >= i; j--) {
                if (nums[j] < nums[j - 1]) {
                    int tem = nums[j];
                    nums[j] = nums[j - 1];
                    nums[j - 1] = tem;
                }
            }
        }
    }

    /**
     * 最优 O(n) 写法
     */
    static void bubbleOn(int[] nums) {
        int n = nums.length;
        for (int i = n - 1; i > 0; i--) {
            boolean flag = true;
            for (int j = 0; j < i; j++)
                if (nums[j] > nums[j + 1]) {
                    int tmp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = tmp;
                    flag = false;
                }
            if (flag) break;
        }
    }

}
